{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check if an Original String Exists Given Two Encoded Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: possiblyEquals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #同源字符串检测"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>原字符串由小写字母组成，可以按下述步骤编码：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>任意将其 <strong>分割</strong> 为由若干 <strong>非空</strong> 子字符串组成的一个 <strong>序列</strong> 。</li>\n",
    "\t<li>任意选择序列中的一些元素（也可能不选择），然后将这些元素替换为元素各自的长度（作为一个数字型的字符串）。</li>\n",
    "\t<li>重新 <strong>顺次连接</strong> 序列，得到编码后的字符串。</li>\n",
    "</ul>\n",
    "\n",
    "<p>例如，编码 <code>\"abcdefghijklmnop\"</code> 的一种方法可以描述为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>将原字符串分割得到一个序列：<code>[\"ab\", \"cdefghijklmn\", \"o\", \"p\"]</code> 。</li>\n",
    "\t<li>选出其中第二个和第三个元素并分别替换为它们自身的长度。序列变为 <code>[\"ab\", \"12\", \"1\", \"p\"]</code> 。</li>\n",
    "\t<li>重新顺次连接序列中的元素，得到编码后的字符串：<code>\"ab121p\"</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你两个编码后的字符串 <code>s1</code> 和 <code>s2</code> ，由小写英文字母和数字 <code>1-9</code> 组成。如果存在能够同时编码得到 <code>s1</code> 和 <code>s2</code> 原字符串，返回 <code>true</code> ；否则，返回 <code>false</code>。</p>\n",
    "\n",
    "<p><strong>注意：</strong>生成的测试用例满足 <code>s1</code> 和 <code>s2</code> 中连续数字数不超过 <code>3</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s1 = \"internationalization\", s2 = \"i18n\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>\"internationalization\" 可以作为原字符串\n",
    "- \"internationalization\" \n",
    "  -&gt; 分割：      [\"internationalization\"]\n",
    "  -&gt; 不替换任何元素\n",
    "  -&gt; 连接：      \"internationalization\"，得到 s1\n",
    "- \"internationalization\"\n",
    "  -&gt; 分割：      [\"i\", \"nternationalizatio\", \"n\"]\n",
    "  -&gt; 替换：      [\"i\", \"18\",                 \"n\"]\n",
    "  -&gt; 连接：      \"i18n\"，得到 s2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s1 = \"l123e\", s2 = \"44\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>\"leetcode\" 可以作为原字符串\n",
    "- \"leetcode\" \n",
    "  -&gt; 分割：       [\"l\", \"e\", \"et\", \"cod\", \"e\"]\n",
    "  -&gt; 替换：       [\"l\", \"1\", \"2\",  \"3\",   \"e\"]\n",
    "  -&gt; 连接：       \"l123e\"，得到 s1\n",
    "- \"leetcode\" \n",
    "  -&gt; 分割：       [\"leet\", \"code\"]\n",
    "  -&gt; 替换：       [\"4\",    \"4\"]\n",
    "  -&gt; 连接：       \"44\"，得到 s2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s1 = \"a5b\", s2 = \"c5b\"\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>不存在这样的原字符串\n",
    "- 编码为 s1 的字符串必须以字母 'a' 开头\n",
    "- 编码为 s2 的字符串必须以字母 'c' 开头\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s1 = \"112s\", s2 = \"g841\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>\"gaaaaaaaaaaaas\" 可以作为原字符串\n",
    "- \"gaaaaaaaaaaaas\"\n",
    "  -&gt; 分割：       [\"g\", \"aaaaaaaaaaaa\", \"s\"]\n",
    "  -&gt; 替换：       [\"1\", \"12\",           \"s\"]\n",
    "  -&gt; 连接：       \"112s\"，得到 s1\n",
    "- \"gaaaaaaaaaaaas\"\n",
    "  -&gt; 分割：       [\"g\", \"aaaaaaaa\", \"aaaa\", \"s\"]\n",
    "  -&gt; 替换：       [\"g\", \"8\",        \"4\",    \"1\"]\n",
    "  -&gt; 连接         \"g841\"，得到 s2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s1 = \"ab\", s2 = \"a2\"\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>不存在这样的原字符串\n",
    "- 编码为 s1 的字符串由两个字母组成\n",
    "- 编码为 s2 的字符串由三个字母组成\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s1.length, s2.length &lt;= 40</code></li>\n",
    "\t<li><code>s1</code> 和 <code>s2</code> 仅由数字 <code>1-9</code> 和小写英文字母组成</li>\n",
    "\t<li><code>s1</code> 和 <code>s2</code> 中连续数字数不超过 <code>3</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-an-original-string-exists-given-two-encoded-strings](https://leetcode.cn/problems/check-if-an-original-string-exists-given-two-encoded-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-an-original-string-exists-given-two-encoded-strings](https://leetcode.cn/problems/check-if-an-original-string-exists-given-two-encoded-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"internationalization\"\\n\"i18n\"', '\"l123e\"\\n\"44\"', '\"a5b\"\\n\"c5b\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i: int, j: int, which: int, rest: int) -> bool:\n",
    "            if which == 0:\n",
    "                if j == n:\n",
    "                    return i == m and rest == 0\n",
    "                elif s2[j].isalpha():\n",
    "                    if rest == 0 and i != m and s1[i].isalpha():\n",
    "                        return (dfs(i + 1, j + 1, 0, 0) if s1[i] == s2[j] else False)\n",
    "                    else:\n",
    "                        return (dfs(i, j + 1, 0, rest - 1) if rest >= 1 else dfs(i, j + 1, 1, 1))\n",
    "                else:\n",
    "                    x, k = 0, j\n",
    "                    while k < n and s2[k].isdigit():\n",
    "                        x = x * 10 + int(s2[k])\n",
    "                        if (rest >= x and dfs(i, k + 1, 0, rest - x)) or (rest < x and dfs(i, k + 1, 1, x - rest)):\n",
    "                            return True\n",
    "                        k += 1\n",
    "                    return False\n",
    "            else:\n",
    "                if i == m:\n",
    "                    return j == n and rest == 0\n",
    "                elif s1[i].isalpha():\n",
    "                    if rest == 0 and j != n and s2[j].isalpha():\n",
    "                        return (dfs(i + 1, j + 1, 0, 0) if s1[i] == s2[j] else False)\n",
    "                    else:\n",
    "                        return (dfs(i + 1, j, 1, rest - 1) if rest >= 1 else dfs(i + 1, j, 0, 1))\n",
    "                else:\n",
    "                    x, k = 0, i\n",
    "                    while k < m and s1[k].isdigit():\n",
    "                        x = x * 10 + int(s1[k])\n",
    "                        if (rest >= x and dfs(k + 1, j, 1, rest - x)) or (rest < x and dfs(k + 1, j, 0, x - rest)):\n",
    "                            return True\n",
    "                        k += 1\n",
    "                    return False\n",
    "\n",
    "        ans = dfs(0, 0, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i: int, j: int, which: int, rest: int) -> bool:\n",
    "            if which == 0:\n",
    "                if j == n:\n",
    "                    return i == m and rest == 0\n",
    "                elif s2[j].isalpha():\n",
    "                    if rest == 0 and i != m and s1[i].isalpha():\n",
    "                        return (dfs(i + 1, j + 1, 0, 0) if s1[i] == s2[j] else False)\n",
    "                    else:\n",
    "                        return (dfs(i, j + 1, 0, rest - 1) if rest >= 1 else dfs(i, j + 1, 1, 1))\n",
    "                else:\n",
    "                    x, k = 0, j\n",
    "                    while k < n and s2[k].isdigit():\n",
    "                        x = x * 10 + int(s2[k])\n",
    "                        if (rest >= x and dfs(i, k + 1, 0, rest - x)) or (rest < x and dfs(i, k + 1, 1, x - rest)):\n",
    "                            return True\n",
    "                        k += 1\n",
    "                    return False\n",
    "            else:\n",
    "                if i == m:\n",
    "                    return j == n and rest == 0\n",
    "                elif s1[i].isalpha():\n",
    "                    if rest == 0 and j != n and s2[j].isalpha():\n",
    "                        return (dfs(i + 1, j + 1, 0, 0) if s1[i] == s2[j] else False)\n",
    "                    else:\n",
    "                        return (dfs(i + 1, j, 1, rest - 1) if rest >= 1 else dfs(i + 1, j, 0, 1))\n",
    "                else:\n",
    "                    x, k = 0, i\n",
    "                    while k < m and s1[k].isdigit():\n",
    "                        x = x * 10 + int(s1[k])\n",
    "                        if (rest >= x and dfs(k + 1, j, 1, rest - x)) or (rest < x and dfs(k + 1, j, 0, x - rest)):\n",
    "                            return True\n",
    "                        k += 1\n",
    "                    return False\n",
    "\n",
    "        ans = dfs(0, 0, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "        m, n=len(s1), len(s2)\n",
    "        dp=[[set() for _ in range(n+1)] for _ in range(m+1)]\n",
    "        dp[0][0].add(0)\n",
    "        for i in range(m+1):\n",
    "            for j in range(n+1):\n",
    "                for delta in dp[i][j]:\n",
    "                    if delta<=0:\n",
    "                        num=0\n",
    "                        for p in range(i, min(m, i+3)):\n",
    "                            if s1[p].isdigit():\n",
    "                                num=num*10+ord(s1[p])-ord('0')\n",
    "                                dp[p+1][j].add(num+delta)\n",
    "                            else:\n",
    "                                break\n",
    "                    if delta>=0:\n",
    "                        num=0\n",
    "                        for q in range(j, min(n, j+3)):\n",
    "                            if s2[q].isdigit():\n",
    "                                num=num*10+ord(s2[q])-ord('0')\n",
    "                                dp[i][q+1].add(delta-num)\n",
    "                            else:\n",
    "                                break\n",
    "                    if delta<0 and i+1<=m and s1[i].isalpha():\n",
    "                        dp[i+1][j].add(delta+1)\n",
    "                    if delta>0 and j+1<=n and s2[j].isalpha():\n",
    "                        dp[i][j+1].add(delta-1)\n",
    "                    if delta==0 and i+1<=m and j+1<=n and s1[i]==s2[j]:\n",
    "                        dp[i+1][j+1].add(0)\n",
    "                    \n",
    "        if 0 in dp[m][n]:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "        m, n=len(s1),len(s2)\n",
    "        dp=[[set() for _ in range(n+1)] for _ in range(m+1)]\n",
    "        dp[0][0].add(0)\n",
    "        for i in range(m+1):\n",
    "            for j in range(n+1):\n",
    "                for delta in dp[i][j]:\n",
    "                    if delta<=0:\n",
    "                        num=0\n",
    "                        for p in range(i, min(i+3,m)):\n",
    "                            if s1[p].isdigit():\n",
    "                                num=num*10+ord(s1[p])-ord('0')\n",
    "                                dp[p+1][j].add(delta+num)\n",
    "                            else:\n",
    "                                break\n",
    "                    if delta>=0:\n",
    "                        num=0\n",
    "                        for q in range(j, min(j+3,n)):\n",
    "                            if s2[q].isdigit():\n",
    "                                num=num*10+ord(s2[q])-ord('0')\n",
    "                                dp[i][q+1].add(delta-num)\n",
    "                            else:\n",
    "                                break\n",
    "                    if delta>0 and j+1<=n and s2[j].isalpha():\n",
    "                        dp[i][j+1].add(delta-1)\n",
    "                    if delta<0 and i+1<=m and s1[i].isalpha():\n",
    "                        dp[i+1][j].add(delta+1)\n",
    "                    if delta==0 and i+1<=m and j+1<=n and s1[i]==s2[j]:\n",
    "                        dp[i+1][j+1].add(0)\n",
    "\n",
    "        if 0 in dp[m][n]:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "        dp = [[set() for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "\n",
    "        arr1, arr2 = list(s1), list(s2)\n",
    "\n",
    "        dp[0][0].add(0)\n",
    "        for i in range(m + 1):\n",
    "            for j in range(n + 1):\n",
    "                for diff in dp[i][j]:\n",
    "                    # s1 is a number\n",
    "                    num = 0\n",
    "                    k = i\n",
    "                    while k < min(i + 3, m) and self.isNum(arr1[k]):\n",
    "                        num = num * 10 + int(arr1[k])\n",
    "                        dp[k + 1][j].add(diff + num)\n",
    "                        k += 1\n",
    "\n",
    "                    # s2 is a number\n",
    "                    num = 0\n",
    "                    k = j\n",
    "                    while k < min(j + 3, n) and self.isNum(arr2[k]):\n",
    "                        num = num * 10 + int(arr2[k])\n",
    "                        dp[i][k + 1].add(diff - num)\n",
    "                        k += 1\n",
    "\n",
    "                    # Number matches letter in s1\n",
    "                    if i < m and not self.isNum(arr1[i]) and diff < 0:\n",
    "                        dp[i + 1][j].add(diff + 1)\n",
    "\n",
    "                    # Number matches letter in s2\n",
    "                    if j < n and not self.isNum(arr2[j]) and diff > 0:\n",
    "                        dp[i][j + 1].add(diff - 1)\n",
    "\n",
    "                    # Both letters match\n",
    "                    if i < m and j < n and not self.isNum(arr1[i]) and arr1[i] == arr2[j] and diff == 0:\n",
    "                        dp[i + 1][j + 1].add(diff)\n",
    "\n",
    "        return 0 in dp[m][n]\n",
    "\n",
    "    def isNum(self, c: str) -> bool:\n",
    "        return '0' <= c <= '9'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, which, rest):\n",
    "            if which == 0:\n",
    "                # 递归结束条件\n",
    "                if j == n:\n",
    "                    return i == m and rest == 0\n",
    "                # 如果 s2[j] 是字母\n",
    "                elif s2[j].isalpha():\n",
    "                    # 如果 s1[i] 也是字母且剩余为 0, 此时直接判断 s1[i] == s2[j]\n",
    "                    if i != m and s1[i].isalpha() and rest == 0:\n",
    "                        return (dfs(i + 1, j + 1, 0, 0) if s1[i] == s2[j] else False)\n",
    "                    # rest 还有, 则消耗一个\n",
    "                    elif rest >= 1:\n",
    "                        return dfs(i, j + 1, 0, rest - 1)\n",
    "                    # 后面剩下的情况: rest 为 0, 且 i == m 或者 s1[i] 不是字母, 此时转为 s2 多余 1 字符\n",
    "                    else:\n",
    "                        return dfs(i, j + 1, 1, 1)\n",
    "                # s2[j] 是数字\n",
    "                else:\n",
    "                    x, k = 0, j\n",
    "                    while k < n and s2[k].isdigit():\n",
    "                        x = x * 10 + int(s2[k])\n",
    "                        # 尝试消耗 rest\n",
    "                        if (rest >= x and dfs(i, k + 1, 0, rest - x)) or (rest < x and dfs(i, k + 1, 1, x - rest)):\n",
    "                            return True\n",
    "                        k += 1\n",
    "                    return False\n",
    "            else:\n",
    "                if i == m:\n",
    "                    return j == n and rest == 0\n",
    "                elif s1[i].isalpha():\n",
    "                    if j != n and s2[j].isalpha() and rest == 0:\n",
    "                        return (dfs(i + 1, j + 1, 0, 0) if s1[i] == s2[j] else False)\n",
    "                    elif rest >= 1:\n",
    "                        return dfs(i + 1, j, 1, rest - 1)\n",
    "                    else:\n",
    "                        return dfs(i + 1, j, 0, 1)\n",
    "                else:\n",
    "                    x, k = 0, i\n",
    "                    while k < m and s1[k].isdigit():\n",
    "                        x = x * 10 + int(s1[k])\n",
    "                        if (rest >= x and dfs(k + 1, j, 1, rest - x)) or (rest < x and dfs(k + 1, j, 0, x - rest)):\n",
    "                            return True\n",
    "                        k += 1\n",
    "                    return False\n",
    "\n",
    "        ans = dfs(0, 0, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i: int, j: int, which: int, rest: int) -> bool:\n",
    "            if which == 0:\n",
    "                if j == n:\n",
    "                    return i == m and rest == 0\n",
    "                elif s2[j].isalpha():\n",
    "                    if rest == 0 and i != m and s1[i].isalpha():\n",
    "                        return (dfs(i + 1, j + 1, 0, 0) if s1[i] == s2[j] else False)\n",
    "                    else:\n",
    "                        return (dfs(i, j + 1, 0, rest - 1) if rest >= 1 else dfs(i, j + 1, 1, 1))\n",
    "                else:\n",
    "                    x, k = 0, j\n",
    "                    while k < n and s2[k].isdigit():\n",
    "                        x = x * 10 + int(s2[k])\n",
    "                        if (rest >= x and dfs(i, k + 1, 0, rest - x)) or (rest < x and dfs(i, k + 1, 1, x - rest)):\n",
    "                            return True\n",
    "                        k += 1\n",
    "                    return False\n",
    "            else:\n",
    "                if i == m:\n",
    "                    return j == n and rest == 0\n",
    "                elif s1[i].isalpha():\n",
    "                    if rest == 0 and j != n and s2[j].isalpha():\n",
    "                        return (dfs(i + 1, j + 1, 0, 0) if s1[i] == s2[j] else False)\n",
    "                    else:\n",
    "                        return (dfs(i + 1, j, 1, rest - 1) if rest >= 1 else dfs(i + 1, j, 0, 1))\n",
    "                else:\n",
    "                    x, k = 0, i\n",
    "                    while k < m and s1[k].isdigit():\n",
    "                        x = x * 10 + int(s1[k])\n",
    "                        if (rest >= x and dfs(k + 1, j, 1, rest - x)) or (rest < x and dfs(k + 1, j, 0, x - rest)):\n",
    "                            return True\n",
    "                        k += 1\n",
    "                    return False\n",
    "\n",
    "        ans = dfs(0, 0, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i: int, j: int, which: int, rest: int) -> bool:\n",
    "            if which == 0:\n",
    "                if j == n:\n",
    "                    return i == m and rest == 0\n",
    "                elif s2[j].isalpha():\n",
    "                    if rest == 0 and i != m and s1[i].isalpha():\n",
    "                        return (dfs(i + 1, j + 1, 0, 0) if s1[i] == s2[j] else False)\n",
    "                    else:\n",
    "                        return (dfs(i, j + 1, 0, rest - 1) if rest >= 1 else dfs(i, j + 1, 1, 1))\n",
    "                else:\n",
    "                    x, k = 0, j\n",
    "                    while k < n and s2[k].isdigit():\n",
    "                        x = x * 10 + int(s2[k])\n",
    "                        if (rest >= x and dfs(i, k + 1, 0, rest - x)) or (rest < x and dfs(i, k + 1, 1, x - rest)):\n",
    "                            return True\n",
    "                        k += 1\n",
    "                    return False\n",
    "            else:\n",
    "                if i == m:\n",
    "                    return j == n and rest == 0\n",
    "                elif s1[i].isalpha():\n",
    "                    if rest == 0 and j != n and s2[j].isalpha():\n",
    "                        return (dfs(i + 1, j + 1, 0, 0) if s1[i] == s2[j] else False)\n",
    "                    else:\n",
    "                        return (dfs(i + 1, j, 1, rest - 1) if rest >= 1 else dfs(i + 1, j, 0, 1))\n",
    "                else:\n",
    "                    x, k = 0, i\n",
    "                    while k < m and s1[k].isdigit():\n",
    "                        x = x * 10 + int(s1[k])\n",
    "                        if (rest >= x and dfs(k + 1, j, 1, rest - x)) or (rest < x and dfs(k + 1, j, 0, x - rest)):\n",
    "                            return True\n",
    "                        k += 1\n",
    "                    return False\n",
    "\n",
    "        ans = dfs(0, 0, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i: int, j: int, which: int, rest: int) -> bool:\n",
    "            if which == 0:\n",
    "                if j == n:\n",
    "                    return i == m and rest == 0\n",
    "                elif s2[j].isalpha():\n",
    "                    if rest == 0 and i != m and s1[i].isalpha():\n",
    "                        return (dfs(i + 1, j + 1, 0, 0) if s1[i] == s2[j] else False)\n",
    "                    else:\n",
    "                        return (dfs(i, j + 1, 0, rest - 1) if rest >= 1 else dfs(i, j + 1, 1, 1))\n",
    "                else:\n",
    "                    x, k = 0, j\n",
    "                    while k < n and s2[k].isdigit():\n",
    "                        x = x * 10 + int(s2[k])\n",
    "                        if (rest >= x and dfs(i, k + 1, 0, rest - x)) or (rest < x and dfs(i, k + 1, 1, x - rest)):\n",
    "                            return True\n",
    "                        k += 1\n",
    "                    return False\n",
    "            else:\n",
    "                if i == m:\n",
    "                    return j == n and rest == 0\n",
    "                elif s1[i].isalpha():\n",
    "                    if rest == 0 and j != n and s2[j].isalpha():\n",
    "                        return (dfs(i + 1, j + 1, 0, 0) if s1[i] == s2[j] else False)\n",
    "                    else:\n",
    "                        return (dfs(i + 1, j, 1, rest - 1) if rest >= 1 else dfs(i + 1, j, 0, 1))\n",
    "                else:\n",
    "                    x, k = 0, i\n",
    "                    while k < m and s1[k].isdigit():\n",
    "                        x = x * 10 + int(s1[k])\n",
    "                        if (rest >= x and dfs(k + 1, j, 1, rest - x)) or (rest < x and dfs(k + 1, j, 0, x - rest)):\n",
    "                            return True\n",
    "                        k += 1\n",
    "                    return False\n",
    "\n",
    "        ans = dfs(0, 0, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "\n",
    "        def check(st):\n",
    "            if len(st) == 1:\n",
    "                return [int(st)]\n",
    "            if len(st) == 2:\n",
    "                return [int(st), int(st[0]) + int(st[1])]\n",
    "            return [int(st), int(st[:2]) + int(st[2]), int(st[0]) + int(st[1:]), int(st[0]) + int(st[1]) + int(st[2])]\n",
    "\n",
    "        def depart(s):\n",
    "            k = len(s)\n",
    "            i = 0\n",
    "            res = []\n",
    "            while i < k:\n",
    "                if s[i].isnumeric():\n",
    "                    cur = \"\"\n",
    "                    while i < k and s[i].isnumeric():\n",
    "                        cur += s[i]\n",
    "                        i += 1\n",
    "                    res.append([str(x) for x in check(cur)])\n",
    "                else:\n",
    "                    res.append([s[i]])\n",
    "                    i += 1\n",
    "            post = []\n",
    "            for ls in res:\n",
    "                post.append(max(int(w) if w.isnumeric() else 1 for w in ls))\n",
    "            return res, list(accumulate(post, initial=0))\n",
    "\n",
    "        lst1, pre1 = depart(s1)\n",
    "        lst2, pre2 = depart(s2)\n",
    "        m, n = len(lst1), len(lst2)\n",
    "\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, x):\n",
    "            if pre2[-1] - pre2[j] < x:\n",
    "                return False\n",
    "            if pre1[-1] - pre1[i] < -x:\n",
    "                return False\n",
    "            \n",
    "            if x == 0:\n",
    "                if i == m and j == n:\n",
    "                    return True\n",
    "                if i == m or j == n:\n",
    "                    return False\n",
    "                for a in lst1[i]:\n",
    "                    for b in lst2[j]:\n",
    "                        if a.isnumeric() and b.isnumeric():\n",
    "                            if dfs(i + 1, j + 1, int(a) - int(b)):\n",
    "                                return True\n",
    "                        elif not a.isnumeric() and not b.isnumeric():\n",
    "                            if a == b and dfs(i + 1, j + 1, 0):\n",
    "                                return True\n",
    "                        elif a.isnumeric() and not b.isnumeric():\n",
    "                            if dfs(i + 1, j + 1, int(a) - 1):\n",
    "                                return True\n",
    "                        else:\n",
    "                            if dfs(i + 1, j + 1, 1 - int(b)):\n",
    "                                return True\n",
    "                return False\n",
    "            elif x > 0:\n",
    "                if j == n:\n",
    "                    return False\n",
    "                for b in lst2[j]:\n",
    "                    if b.isnumeric() and dfs(i, j + 1, x - int(b)):\n",
    "                        return True\n",
    "                    if not b.isnumeric() and dfs(i, j + 1, x - 1):\n",
    "                        return True\n",
    "            else:\n",
    "                if i == m:\n",
    "                    return False\n",
    "                for a in lst1[i]:\n",
    "                    if a.isnumeric() and dfs(i + 1, j, x + int(a)):\n",
    "                        return True\n",
    "                    if not a.isnumeric() and dfs(i + 1, j, x + 1):\n",
    "                        return True\n",
    "            return\n",
    "\n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "\n",
    "        def check(st):\n",
    "            if len(st) == 1:\n",
    "                return [int(st)]\n",
    "            if len(st) == 2:\n",
    "                return [int(st), int(st[0])+int(st[1])]\n",
    "            return [int(st), int(st[:2])+int(st[2]), int(st[0])+int(st[1:]), int(st[0])+int(st[1])+int(st[2])]\n",
    "\n",
    "        def depart(s):\n",
    "            k = len(s)\n",
    "            i = 0\n",
    "            res = []\n",
    "            while i < k:\n",
    "                if s[i].isnumeric():\n",
    "                    cur = \"\"\n",
    "                    while i < k and s[i].isnumeric():\n",
    "                        cur += s[i]\n",
    "                        i += 1\n",
    "                    res.append([str(x) for x in check(cur)])\n",
    "                else:\n",
    "                    res.append([s[i]])\n",
    "                    i += 1\n",
    "            return res\n",
    "\n",
    "        lst1 = depart(s1)\n",
    "        lst2 = depart(s2)\n",
    "        m, n = len(lst1), len(lst2)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, x):\n",
    "            if x == 0:\n",
    "                if i == m and j == n:\n",
    "                    return True\n",
    "                if i == m or j == n:\n",
    "                    return False\n",
    "                for a in lst1[i]:\n",
    "                    for b in lst2[j]:\n",
    "                        if a.isnumeric() and b.isnumeric():\n",
    "                            if dfs(i+1, j+1, int(a)-int(b)):\n",
    "                                return True\n",
    "                        if not a.isnumeric() and not b.isnumeric():\n",
    "                            if a == b and dfs(i+1, j+1, 0):\n",
    "                                return True\n",
    "                        if a.isnumeric() and not b.isnumeric() and dfs(i+1, j+1, int(a)-1):\n",
    "                            return True\n",
    "                        if b.isnumeric() and not a.isnumeric() and dfs(i+1, j+1, 1 - int(b)):\n",
    "                            return True\n",
    "                return False\n",
    "            if x > 0:\n",
    "                if j == n:\n",
    "                    return False\n",
    "                for b in lst2[j]:\n",
    "                    if b.isnumeric() and dfs(i, j+1, x-int(b)):\n",
    "                        return True\n",
    "                    if not b.isnumeric() and dfs(i, j+1, x - 1):\n",
    "                        return True\n",
    "            else:\n",
    "                if i == m:\n",
    "                    return False\n",
    "                for a in lst1[i]:\n",
    "                    if a.isnumeric() and dfs(i+1, j, x + int(a)):\n",
    "                        return True\n",
    "                    if not a.isnumeric() and dfs(i+1, j, x + 1):\n",
    "                        return True\n",
    "            return\n",
    "\n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "        def cal(l):\n",
    "            if len(l) == 1:\n",
    "                return [l[0]]\n",
    "            if len(l) == 2:\n",
    "                return [10 * l[0] + l[1],l[0] + l[1]]\n",
    "            \n",
    "            return [l[0] + l[1] + l[2],100 * l[0] + 10 * l[1] + l[2],l[0] + 10 * l[1] + l[2],10 * l[0] + l[1] + l[2]]\n",
    "        \n",
    "        m,n = len(s1),len(s2)\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j,diff):\n",
    "            if i == m and j == n:\n",
    "                return diff == 0\n",
    "            ans = False\n",
    "            if diff > 0:\n",
    "                if j == n:\n",
    "                    return False\n",
    "                temp = []\n",
    "                if s2[j].isalpha():\n",
    "                    temp.append(1)\n",
    "                    j += 1\n",
    "                else:\n",
    "                    while j < n and s2[j].isdigit():\n",
    "                        temp.append(int(s2[j]))\n",
    "                        j += 1\n",
    "                for c in cal(temp):\n",
    "                    ans = ans | dfs(i,j,diff - c)\n",
    "            elif diff < 0:\n",
    "                if i == m:\n",
    "                    return False\n",
    "                temp = []\n",
    "                if s1[i].isalpha():\n",
    "                    temp.append(1)\n",
    "                    i += 1\n",
    "                else:\n",
    "                    while i < m and s1[i].isdigit():\n",
    "                        temp.append(int(s1[i]))\n",
    "                        i += 1\n",
    "                for c in cal(temp):\n",
    "                    ans = ans | dfs(i,j,diff + c)\n",
    "            else:\n",
    "                if i == m or j == n:\n",
    "                    return False\n",
    "                if s1[i].isalpha() and s2[j].isalpha():\n",
    "                    return dfs(i + 1,j + 1,diff) if s1[i] == s2[j] else False\n",
    "                t1,t2 = [],[]\n",
    "                if s1[i].isalpha():\n",
    "                    t1.append(1)\n",
    "                    i += 1\n",
    "                else:\n",
    "                    while i < m and s1[i].isdigit():\n",
    "                        t1.append(int(s1[i]))\n",
    "                        i += 1\n",
    "                if s2[j].isalpha():\n",
    "                    t2.append(1)\n",
    "                    j += 1\n",
    "                else:\n",
    "                    while j < n and s2[j].isdigit():\n",
    "                        t2.append(int(s2[j]))\n",
    "                        j += 1\n",
    "                for n1 in cal(t1):\n",
    "                    for n2 in cal(t2):\n",
    "                        ans = ans | dfs(i,j,n1 - n2)\n",
    "            return ans\n",
    "        return dfs(0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "        l1, l2 = len(s1), len(s2)\n",
    "        # print(l1, l2)\n",
    "        rec = {}\n",
    "        def work(i, j, surplus):\n",
    "            if (i, j, surplus) in rec:\n",
    "                return rec[(i, j, surplus)]\n",
    "            if i >= len(s1) and j >= len(s2):\n",
    "                return surplus == 0\n",
    "            res = False\n",
    "            if i >= len(s1):\n",
    "                if surplus < 0:\n",
    "                    res = False\n",
    "                elif 'a' <= s2[j] <= 'z':\n",
    "                    res = work(i, j+1, surplus-1)\n",
    "                else:\n",
    "                    k, t = j, 0\n",
    "                    while k < len(s2) and '0' <= s2[k] <= '9':\n",
    "                        t = 10 * t + int(s2[k])\n",
    "                        k += 1\n",
    "                        res = res or work(i, k, surplus - t)\n",
    "                        if res:\n",
    "                            break\n",
    "            elif j >= len(s2):\n",
    "                if surplus > 0:\n",
    "                    res = False\n",
    "                elif 'a' <= s1[i] <= 'z':\n",
    "                    res = work(i+1, j, surplus+1)\n",
    "                else:\n",
    "                    k, t = i, 0\n",
    "                    while k < len(s1) and '0' <= s1[k] <= '9':\n",
    "                        t = 10 * t + int(s1[k])\n",
    "                        k += 1\n",
    "                        res = res or work(k, j, surplus + t)\n",
    "                        if res:\n",
    "                            break\n",
    "            else:\n",
    "                if 'a' <= s1[i] <= 'z' and 'a' <= s2[j] <= 'z':\n",
    "                    if surplus == 0:\n",
    "                        if s1[i] == s2[j]:\n",
    "                            res = work(i+1, j+1, surplus)\n",
    "                        else:\n",
    "                            res = False\n",
    "                    elif surplus > 0:\n",
    "                        res = work(i, j+1, surplus-1)\n",
    "                    elif surplus < 0:\n",
    "                        res = work(i+1, j, surplus+1)\n",
    "                elif 'a' <= s1[i] <= 'z':\n",
    "                    if surplus < 0:\n",
    "                        res = work(i+1, j, surplus+1)\n",
    "                    else:\n",
    "                        t, k = 0, j\n",
    "                        while k < len(s2) and '0' <= s2[k] <= '9':\n",
    "                            t = 10 * t + int(s2[k])\n",
    "                            k += 1\n",
    "                            res = res or work(i, k, surplus - t)\n",
    "                            if res: break\n",
    "                elif 'a' <= s2[j] <= 'z':\n",
    "                    if surplus > 0:\n",
    "                        res = work(i, j+1, surplus-1)\n",
    "                    else:\n",
    "                        t, k = 0, i\n",
    "                        while k < len(s1) and '0' <= s1[k] <= '9':\n",
    "                            t = 10 * t + int(s1[k])\n",
    "                            k += 1\n",
    "                            res = res or work(k, j, surplus + t)\n",
    "                            if res: break\n",
    "                else:\n",
    "                    t1l, t2l, k1, k2, t1, t2 = [], [], i, j, 0, 0\n",
    "                    while k1 < len(s1) and '0' <= s1[k1] <= '9':\n",
    "                        t1 = 10 * t1 + int(s1[k1])\n",
    "                        k1 += 1\n",
    "                        t1l.append(t1)\n",
    "                    while k2 < len(s2) and '0' <= s2[k2] <= '9':\n",
    "                        t2 = 10 * t2 + int(s2[k2])\n",
    "                        k2 += 1\n",
    "                        t2l.append(t2)\n",
    "                    for z1, t1 in enumerate(t1l):\n",
    "                        for z2, t2 in enumerate(t2l):\n",
    "                            res = res or work(i + z1 + 1, j + z2 + 1, surplus + t1 - t2)\n",
    "                            if res:\n",
    "                                break\n",
    "                        if res:\n",
    "                            break\n",
    "\n",
    "            rec[(i, j, surplus)] = res\n",
    "            return res  \n",
    "        \n",
    "        a = work(0, 0, 0)\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, longer, rest):\n",
    "            '''\n",
    "            longer = 1:表示当前真实长度s1更长，rest为s1比s2多出的字符数\n",
    "            longer = 2:表示当前真实长度s2更长，rest为s2比s1多出的字符数\n",
    "            '''\n",
    "            # 当前是s1更长，拓展s2寻求匹配\n",
    "            if longer == 1:\n",
    "                # s2已到结尾，返回匹配结果\n",
    "                if j == n:\n",
    "                    return (i == m and rest == 0)\n",
    "                # s2未到结尾，且s2[j]为字母\n",
    "                elif s2[j].isalpha():\n",
    "                    # 已遍历s1末尾字符为字母，需要完全匹配\n",
    "                    if i > 0 and rest == 1 and s1[i-1].isalpha():\n",
    "                        return (s1[i-1] == s2[j] and dfs(i, j+1, 1, 0))\n",
    "                    # 已遍历s1末尾字符为数字，消耗一个rest\n",
    "                    else:\n",
    "                        # 剩余rest大于0，直接消耗一个rest\n",
    "                        if rest > 0:\n",
    "                            return dfs(i, j+1, 1, rest-1)\n",
    "                        # 剩余rest等于0，状况变为s2更长\n",
    "                        else:\n",
    "                            return dfs(i, j+1, 2, 1)\n",
    "                # s2未到结尾，且s2[j]为数字\n",
    "                else:\n",
    "                    cnt = 0\n",
    "                    while j+cnt < n and s2[j+cnt].isdigit():\n",
    "                        curVal = int(s2[j:j+cnt+1])\n",
    "                        if curVal <= rest and dfs(i, j+cnt+1, 1, rest-curVal):\n",
    "                            return True\n",
    "                        if curVal > rest and dfs(i, j+cnt+1, 2, curVal-rest):\n",
    "                            return True\n",
    "                        cnt += 1\n",
    "            # 当前是s2更长，拓展s1寻求匹配\n",
    "            else:\n",
    "                # s1到达结尾，直接返回结果\n",
    "                if i == m:\n",
    "                    return (j == n and rest == 0)\n",
    "                # s1未到结尾，且s1末尾为字母\n",
    "                elif s1[i].isalpha():\n",
    "                    # 已匹配s2末尾为字母\n",
    "                    if j > 0 and rest == 1 and s2[j-1].isalpha():\n",
    "                        return (s1[i] == s2[j-1] and dfs(i+1, j, 1, 0))\n",
    "                    # 已匹配s2末尾为数字\n",
    "                    else:\n",
    "                        if rest > 1:\n",
    "                            return dfs(i+1, j, 2, rest-1)\n",
    "                        else:\n",
    "                            return dfs(i+1, j, 1, 1-rest)\n",
    "                # s1未到结尾，且s1末尾为数字\n",
    "                else:\n",
    "                    cnt = 0\n",
    "                    while i+cnt < m and s1[i+cnt].isdigit():\n",
    "                        curVal = int(s1[i:i+cnt+1])\n",
    "                        if curVal < rest and dfs(i+cnt+1, j, 2, rest-curVal):\n",
    "                            return True\n",
    "                        if curVal >= rest and dfs(i+cnt+1, j, 1, curVal-rest):\n",
    "                            return True\n",
    "                        cnt += 1\n",
    "            return False\n",
    "\n",
    "        return dfs(0, 0, 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, longer, rest):\n",
    "            '''\n",
    "            longer = 1:表示当前真实长度s1更长，rest为s1比s2多出的字符数\n",
    "            longer = 2:表示当前真实长度s2更长，rest为s2比s1多出的字符数\n",
    "            '''\n",
    "            # 当前是s1更长，拓展s2寻求匹配\n",
    "            if longer == 1:\n",
    "                # s2已到结尾，返回匹配结果\n",
    "                if j == n:\n",
    "                    return (i == m and rest == 0)\n",
    "                # s2未到结尾，且s2[j]为字母\n",
    "                elif s2[j].isalpha():\n",
    "                    # 已遍历s1末尾字符为字母，需要完全匹配\n",
    "                    if i > 0 and rest == 1 and s1[i-1].isalpha():\n",
    "                        return (s1[i-1] == s2[j] and dfs(i, j+1, 1, 0))\n",
    "                    # 已遍历s1末尾字符为数字，消耗一个rest\n",
    "                    else:\n",
    "                        # 剩余rest大于0，直接消耗一个rest\n",
    "                        if rest > 0:\n",
    "                            return dfs(i, j+1, 1, rest-1)\n",
    "                        # 剩余rest等于0，状况变为s2更长\n",
    "                        else:\n",
    "                            return dfs(i, j+1, 2, 1)\n",
    "                # s2未到结尾，且s2[j]为字母\n",
    "                else:\n",
    "                    cnt = 0\n",
    "                    while j+cnt < n and s2[j+cnt].isdigit():\n",
    "                        curVal = int(s2[j:j+cnt+1])\n",
    "                        if curVal <= rest and dfs(i, j+cnt+1, 1, rest-curVal):\n",
    "                            return True\n",
    "                        if curVal > rest and dfs(i, j+cnt+1, 2, curVal-rest):\n",
    "                            return True\n",
    "                        cnt += 1\n",
    "            # 当前是s2更长，拓展s1寻求匹配\n",
    "            else:\n",
    "                # s1到达结尾，直接返回结果\n",
    "                if i == m:\n",
    "                    return (j == n and rest == 0)\n",
    "                # s1未到结尾，且s1末尾为字母\n",
    "                elif s1[i].isalpha():\n",
    "                    # 已匹配s2末尾为字母\n",
    "                    if j > 0 and rest == 1 and s2[j-1].isalpha():\n",
    "                        return (s1[i] == s2[j-1] and dfs(i+1, j, 1, 0))\n",
    "                    # 已匹配s2末尾为数字\n",
    "                    else:\n",
    "                        if rest > 1:\n",
    "                            return dfs(i+1, j, 2, rest-1)\n",
    "                        else:\n",
    "                            return dfs(i+1, j, 1, 1-rest)\n",
    "                # s1未到结尾，且s1末尾为数字\n",
    "                else:\n",
    "                    cnt = 0\n",
    "                    while i+cnt < m and s1[i+cnt].isdigit():\n",
    "                        curVal = int(s1[i:i+cnt+1])\n",
    "                        if curVal < rest and dfs(i+cnt+1, j, 2, rest-curVal):\n",
    "                            return True\n",
    "                        if curVal >= rest and dfs(i+cnt+1, j, 1, curVal-rest):\n",
    "                            return True\n",
    "                        cnt += 1\n",
    "            return False\n",
    "\n",
    "        return dfs(0, 0, 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "        @cache\n",
    "        def dp(i, j, which, rest):\n",
    "            #print(i, j, which, rest)\n",
    "            # if rest > 999:\n",
    "            #     return False\n",
    "\n",
    "            if which == 0:\n",
    "                if i == m:\n",
    "                    return j == n and rest == 0\n",
    "                \n",
    "                elif s1[i].isalpha():\n",
    "                    if rest == 0 and j < n and s2[j].isalpha():\n",
    "                        if s1[i] == s2[j]:\n",
    "                            return dp(i + 1, j + 1, 0, 0)\n",
    "                        else:\n",
    "                            return False\n",
    "                    elif rest > 0:\n",
    "                        return dp(i + 1, j, 0, rest - 1)\n",
    "                    else:\n",
    "                        return dp(i + 1, j, 1, 1)\n",
    "\n",
    "                else:\n",
    "                    c = i\n",
    "                    while c < m and s1[c].isdigit():\n",
    "                        x = int(s1[i: c + 1])\n",
    "\n",
    "                        if x <= rest and dp(c + 1, j, 0, rest - x):\n",
    "                            return True\n",
    "                        elif x > rest and dp(c + 1, j, 1, x - rest):\n",
    "                            return True\n",
    "\n",
    "                        c += 1\n",
    "                    return False\n",
    "            else:\n",
    "                if j == n:\n",
    "                    return i == m and rest == 0\n",
    "\n",
    "                elif s2[j].isalpha():\n",
    "                    if rest == 0 and i < m and s1[i].isalpha():\n",
    "                        if s1[i] == s2[j]:\n",
    "                            return dp(i + 1, j + 1, 1, 0)\n",
    "                        else:\n",
    "                            return False\n",
    "                    elif rest > 0:\n",
    "                        return dp(i, j + 1, 1, rest - 1)\n",
    "                    else:\n",
    "                        return dp(i, j + 1, 0, 1)\n",
    "                \n",
    "                else:\n",
    "                    d = j\n",
    "                    while d < n and s2[d].isdigit():\n",
    "                        x = int(s2[j: d + 1])\n",
    "\n",
    "                        if x <= rest and dp(i, d + 1, 1, rest - x):\n",
    "                            return True\n",
    "                        elif x > rest and dp(i, d + 1, 0, x - rest):\n",
    "                            return True\n",
    "                        d += 1\n",
    "                    return False\n",
    "\n",
    "        return dp(0, 0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def possiblyEquals(self, s1: str, s2: str) -> bool:\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(str1, str2, delta):\n",
    "            if not str1 and not str2:\n",
    "                return delta == 0\n",
    "            if delta < 0:\n",
    "                str1, str2 = str2, str1\n",
    "                delta = -delta\n",
    "            if delta > 0:\n",
    "                if not str2:\n",
    "                    return False\n",
    "                if str2[0].isalpha():\n",
    "                    return dfs(str1, str2[1:], delta - 1)\n",
    "                num = int(str2[0])\n",
    "                if dfs(str1, str2[1:], delta - num):\n",
    "                    return True\n",
    "                if len(str2) > 1 and str2[1].isdigit():\n",
    "                    num = int(str2[:2])\n",
    "                    if dfs(str1, str2[2:], delta - num):\n",
    "                        return True\n",
    "                    if len(str2) > 2 and str2[2].isdigit():\n",
    "                        num = int(str2[:3])\n",
    "                        if dfs(str1, str2[3:], delta - num):\n",
    "                            return True\n",
    "            else:\n",
    "                if not str1 or not str2:\n",
    "                    return False\n",
    "                if str1[0].isalpha():\n",
    "                    if str2[0].isalpha() and str1[0] != str2[0]:\n",
    "                        return False\n",
    "                    return dfs(str1[1:], str2, 1)\n",
    "                num = int(str1[0])\n",
    "                if dfs(str1[1:], str2, num):\n",
    "                    return True\n",
    "                if len(str1) > 1 and str1[1].isdigit():\n",
    "                    num = int(str1[:2])\n",
    "                    if dfs(str1[2:], str2, num):\n",
    "                        return True\n",
    "                    if len(str1) > 2 and str1[2].isdigit():\n",
    "                        num = int(str1[:3])\n",
    "                        if dfs(str1[3:], str2, num):\n",
    "                            return True\n",
    "            return False\n",
    "\n",
    "        return dfs(s1, s2, 0)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
